
/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86183
 * Date: 2022-09-30
 * Time: 15:40
 */

public class TestBinaryTree {
    static class TreeNode{
        char val;
        TreeNode left;
        TreeNode right;
        TreeNode(char val){
            this.val = val;
        }
    }
        //先序遍历
        public void preOrder(TreeNode root){
        if(root == null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
    //中序遍历
    public void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    //后序遍历
    public void postOrder(TreeNode root){
        if(root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }
    //先序遍历创建二叉树
    private int i = 0;
    public TreeNode createTree(String str){
        TreeNode root = null;
        if (str.charAt(i) != '#') {
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        }else {
            i++;
        }
        return root;
    }
    //计算节点个数
    public static int nodesize = 0;
    public int size(TreeNode root){
        if(root == null){
            return 0;
        }
        nodesize++;
        size(root.left);
        size(root.right);
        return nodesize;
    }
    //递归计算节点个数
    public int size2(TreeNode root){
        if(root == null){
            return 0;
        }
        int tmp = size2(root.left) + size2(root.right) + 1;
        return tmp;
    }
    //获取叶子节点的个数
    int getLeafNodeCount(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return  getLeafNodeCount(root.left)
                + getLeafNodeCount(root.right);
    }
    public static int leafsize = 0;
    void getLeafNodecount2(TreeNode root){
        if(root == null){
            return;
        }
        if(root.left == null && root.right == null){
            leafsize++;
        }
        getLeafNodecount2(root.left);
        getLeafNodecount2(root.right);
    }
    //获取第k层节点的个数
    int getKLevelNodeCount(TreeNode root ,int k){
        if(root == null || k <= 0){
            return 0;
        }
        if(k == 1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)
                + getKLevelNodeCount(root.right,k-1);
    }
}
